//https://leetcode.cn/problems/subtree-of-another-tree/description/

class Solution {
public:

    TreeNode* x;
    void check(TreeNode* root, int v)
    {
        if (!root)
            return;
        if (root->val == v)
        {
            x = root;
            return;
        }

        check(root->left, v);
        check(root->right, v);
    }

    bool dfs(TreeNode* a, TreeNode* b)
    {
        if (!a && !b)
            return true;
        if (!a || !b)
            return false;
        if (a->val != b->val)
            return false;

        return dfs(a->left, b->left) && dfs(a->right, b->right);
    }

    bool isSubtree(TreeNode* root, TreeNode* subRoot)
    {
        check(root, subRoot->val);
        while (!dfs(x, subRoot))
        {
            if (!x)
                break;
            TreeNode* tmep = x;
            tmep->val = INT_MIN;
            check(root, subRoot->val);
            if (tmep == x)
                break;
        }
        return dfs(x, subRoot);
    }
};